package _18_剑指OfferII;

public class _072_剑指OfferII求平方根 {

    public static void main(String[] args) {

        _072_剑指OfferII求平方根 v = new _072_剑指OfferII求平方根();

        System.out.println(v.mySqrt(15));

    }

    // 二分求解, 其实可以看做有序数组查找某个元素小于等于其元素
    // 因为对于平方数据 假设 n * n = x, 那么 (n - 1)^2 < x < (n + 1)^2
    public int mySqrt(int x) {
        int begin = 0;
        int end = x;
        int result = 0;
        while (begin <= end) {
            int mid = begin + ((end - begin) >> 1);
            if ((long)mid * mid <= x) { // 向下取整效果，所以结果一定是在小于这变
                result = mid;
                begin = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return result;
    }

}
